In a network topology there are often multiple paths to deliver a packet from one hop to the next. One technique to forward packet to the next hop is equal-cost multi-path routing (ECMP). When there are multiple equal cost paths to the next hop, a router using ECMP can increase bandwidth by load balancing network traffic over multiple paths.
A weighted-cost multi-pathing (WCMP) or weighted ECMP is a technique used for distributing network packet traffic among the next hops in proportion to the available capacity of the links between a network node and the next hop. The paths are assigned weights based on their capacity and are selected to forward packets with a probability proportional to each path's weight. Whenever a path or the associated egress port fails, the weights are updated in proportion to the capacity of the remaining paths.
A router implementing ECMP assigns an egress port to each equal-cost path and keeps the port numbers in a table. The router hashes an n-tuple in each packet header and uses the hash value as an index into the table to identify the corresponding egress port. In the past, WCMP was implemented by assigning weights to each egress path based on the path's capacity. The router maintained a table similar to the ECMP, except the entries for each port is replicated according to the weight given to the corresponding weighted path in order to select paths in proportion to how many times the associated table entries are replicated.
Since replicating entries for assigning weight can exceed the number of table entries, the table is optimized by changing the weights to reduce the number of replications needed in the table. For instance, weights of 4 and 13 in a two-path topology need 17 table entries. By changing the weights to 1 and 4 the number of table entries is reduced to 5 at the cost of introducing errors in the original weights. Other weight reduction algorithms have also been used. Nevertheless, for a large number of paths with different capacities, the number of entries can grow and optimizing the table causes large errors in the assigned weights.